Research Advances in Cloud Computing by Sanjay Chaudhary Gaurav Somani & Rajkumar Buyya

Author:Sanjay Chaudhary, Gaurav Somani & Rajkumar Buyya
Language: eng
Format: epub
Publisher: Springer Singapore, Singapore

2.2 Types of Scheduling

Earlier scheduling types include First-In-First-Out(FIFO) [5], Earliest Deadline First (EDF) [25], Shortest Job First (SJF) [34], and priority scheduling [59]. The different types of scheduling are given as follows.

Batch Scheduling: In batch scheduling, jobs are not scheduled as single entities, rather, jobs are combined into batches and scheduled together. It is mostly employed in clusters that are dedicated for running non-interactive jobs. Batch schedulers are used in applications to avoid memory swapping and they are characterized by high utilization and high latency. Jobs are grouped into predetermined batch sizes and scheduled together [1]. In [40], they identified that large batches are characterized by high machine utilization, but processing a large batch may lead to a bottleneck as more important jobs belonging to a different batch or family could be delayed.

Coscheduling: This involves scheduling related processes or tasks to run in parallel. There are frameworks consisting of dependent tasks or tasks that need to communicate with one other for successful completion, and thus, must be scheduled together [39]. There are distributed applications that require that subtasks should be coordinated and synchronized, thereby bringing about the need for a scheduling mechanism to guarantee this synchronization. Coscheduling solves this problem by ensuring that communicating subtasks are available for interaction when needed. For example, consider an application where a running task needs to send a message to a task that has not been scheduled, the task will keep waiting for a reply that is not forthcoming, which will cause blocking in the execution of the application.

In coscheduling, all tasks or processes from an intra-task dependent framework must be scheduled together so that there can be efficient communication among the tasks. There are two variations of coscheduling namely implicit coscheduling and explicit coscheduling [48]. In explicit coscheduling, all dependent tasks are scheduled at the same time, that is, it is either all the tasks are scheduled together or none of the tasks is scheduled. A global scheduling mechanism is employed in explicit coscheduling. In implicit coscheduling, there is no strict enforcement of the rule that all tasks must be scheduled together, rather, tasks can be scheduled independently using local scheduling but scheduling decisions are made in cooperation.

Gang Scheduling: It is a stricter form of coscheduling where dependent tasks are scheduled simultaneously. The tasks are usually from the same job or framework. Gang scheduling ensures that tasks can communicate with one another at any point in time and are thus scheduled concurrently. In [24], they examined and identified optimal performance conditions and efficient mean response time of jobs while ensuring fairness to different categories of gangs (small and large gangs). The main challenge of gang scheduling is how to achieve high cluster utilization, this is because all the tasks in a gang have to wait till enough machines are available to run all the tasks at once. Resource sharing among running tasks also incurs some overhead in gang scheduling [17]. To solve the inherent problem of the neglect of memory considerations in gang scheduling, a gang scheduling algorithm with memory considerations was proposed in [3].

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.